#leetcode题目295：数据流的中位数
#难度：困难
#时间复杂度：O(logn)
#空间复杂度：O(n)

import heapq
from typing import List
class MedianFinder:
    def __init__(self):
        """
        初始化数据结构
        big: 最大堆，存储较小的一半数字
        small: 最小堆，存储较大的一半数字
        size: 总元素个数
        """
        self.big = []      # 最大堆，存储较小的一半
        self.small = []    # 最小堆，存储较大的一半
        self.size = 0      # 总元素个数

    def addNum(self, num: int) -> None:
        """
        添加数字到数据结构中
        """
        self.size += 1
        
        # 先将数字加入small堆
        heapq.heappush(self.small, num)
        
        # 将small堆的最小值移到big堆
        heapq.heappush(self.big, -heapq.heappop(self.small))
        
        # 保持平衡：big堆最多比small堆多1个元素
        if len(self.big) > len(self.small) + 1:
            heapq.heappush(self.small, -heapq.heappop(self.big))

    def findMedian(self) -> float:
        """
        返回当前中位数
        """
        if self.size % 2 == 0:
            # 偶数个元素，中位数是两个堆顶的平均值
            return (self.small[0] + (-self.big[0])) / 2.0
        else:
            # 奇数个元素，中位数是big堆的堆顶
            return float(-self.big[0])


#测试数据
# 输入
# ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
# [[], [1], [2], [], [3], []]
# 输出
# [null, null, null, 1.5, null, 2.0]

# 解释
# MedianFinder medianFinder = new MedianFinder();
# medianFinder.addNum(1);    // arr = [1]
# medianFinder.addNum(2);    // arr = [1, 2]
# medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
# medianFinder.addNum(3);    // arr[1, 2, 3]
# medianFinder.findMedian(); // return 2.0

medianFinder = MedianFinder()
print(medianFinder.__init__())
print(medianFinder.addNum(1))
print(medianFinder.addNum(2))
print(medianFinder.findMedian())
print(medianFinder.addNum(3))
print(medianFinder.findMedian())
